package cn.xmoit.other;

public class Solution {

	/**
	 * 判断是否是回文字符串
	 * @param head 头节点
	 * @return true or false
	 */
	public static boolean isPalindrome(ListNode head) {
		if (head == null || head.next == null) {
			return true;
		}

		// 定义快指针和慢指针，以及一个逆向指针
		ListNode prev = null;
		ListNode slow = head;
		ListNode fast = head;

		// 快指针一次两步，慢指针一次一步，当快指针走完时，慢指针走到中点位置
		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			ListNode next = slow.next;
			// 把慢指针的next赋成prev，再把当前慢指针记录为prev，慢指针向后移动
			// 作用：将前半部分链表逆序
			slow.next = prev;
			prev = slow;
			slow = next;
		}

		// 经过上面遍历，slow正好在中心点且前半部分都为逆序，将其赋给一个新指针进行反向遍历
		// 当fast不为null时，说明链表长度为奇数，slow正好在中心点，需要从中心点后一位开始判断
		if (fast != null) {
			slow = slow.next;
		}

		// 遍历两个指针，比较对应元素值是否相等
		while (slow != null) {
			if (slow.val != prev.val) {
				return false;
			}
			slow = slow.next;
			prev = prev.next;
		}

		return true;
	}

	public static void main(String[] args) {
		// ListNode n1 = new ListNode(1);
		// ListNode n2 = new ListNode(2);
		// ListNode n3 = new ListNode(3);
		// ListNode n4 = new ListNode(4);
		// ListNode n5 = new ListNode(5);
		// ListNode n6 = new ListNode(4);
		// ListNode n7 = new ListNode(3);
		// ListNode n8 = new ListNode(2);
		// ListNode n9 = new ListNode(1);
		// n1.next = n2;
		// n2.next = n3;
		// n3.next = n4;
		// n4.next = n5;
		// n5.next = n6;
		// n6.next = n7;
		// n7.next = n8;
		// n8.next = n9;
		// System.out.println(isPalindrome(n1));

		ListNode n1 = new ListNode(1);
		ListNode n2 = new ListNode(2);
		ListNode n3 = new ListNode(3);
		ListNode n4 = new ListNode(4);
		ListNode n5 = new ListNode(5);
		n1.next = n2;
		n2.next = n3;
		n3.next = n4;
		n4.next = n5;
		n5.next = n1;
		System.out.println(checkCircle(n1));
	}

	/**
	 * 检测环
	 * @param list head
	 * @return true or false
	 */
	public static boolean checkCircle(ListNode list) {
		if (list == null) {
			return false;
		}

		ListNode fast = list.next;
		ListNode slow = list;

		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			slow = slow.next;

			if (slow == fast) {
				return true;
			}
		}

		return false;
	}

}

class ListNode {

	int val;

	ListNode next;

	ListNode(int x) {
		val = x;
	}

}
